package previous.Test_0228_2;
import java.util.List;
import java.util.Scanner;
/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
     }
  }
public class Solution {
        // 用于记录满足条件的数组状态数量
        static int count;

        public static void main(String[] args) {
            // 创建 Scanner 对象，不过此代码未实际用它读取输入
            Scanner scan = new Scanner(System.in);
            // 定义一个 5x5 的二维数组
            int[][] a = new int[5][5];
            // 初始化数组第一行元素
            a[0][0] = 1;
            a[0][1] = 0;
            a[0][2] = 1;
            a[0][3] = 0;
            a[0][4] = 1;
            // 从第二行第一个元素开始进行深度优先搜索
            dfs(a, 1, 0);
            // 输出满足条件的数组状态数量
            System.out.println(count);
            // 关闭 Scanner 对象，释放资源
            scan.close();
        }
        /**
         * 深度优先搜索方法，用于填充数组元素并统计满足条件的情况
         * @param a 二维数组
         * @param i 当前处理的行索引
         * @param j 当前处理的列索引
         */
        public static void dfs(int[][] a, int i, int j) {
            // 当遍历完所有行（i 达到 5），判断是否满足条件
            if (i == 5) {
                // 如果最后一行第一个元素为 1，计数器加 1
                if (a[4][0] == 1) {
                    count++;
                }
                // 结束当前递归调用
                return;
            }
            // 对当前位置尝试三种逻辑运算（与、异或、或）
            for (int k = 0; k < 3; k++) {
                if (k == 0) {
                    // 当前元素为上一行相邻元素的逻辑与结果
                    a[i][j] = a[i - 1][j] & a[i - 1][j + 1];
                } else if (k == 1) {
                    // 当前元素为上一行相邻元素的逻辑异或结果
                    a[i][j] = a[i - 1][j] ^ a[i - 1][j + 1];
                } else if (k == 2) {
                    // 当前元素为上一行相邻元素的逻辑或结果
                    a[i][j] = a[i - 1][j] | a[i - 1][j + 1];
                }
                // 判断是否到当前行的最后一个元素
                if (j == 4 - i) {
                    // 是最后一个元素，进入下一行的第一个元素继续搜索
                    dfs(a, i + 1, 0);
                } else {
                    // 不是最后一个元素，继续处理当前行的下一个元素
                    dfs(a, i, j + 1);
                }
            }
        }
        //汉若塔问题
        public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            dfs1(A,B,C,A.size());
            return;
        }
        public void dfs1(List<Integer> a, List<Integer> b, List<Integer> c,int n){
            //最后一个盘子的时候，将a上最后一个盘子放到c
            if(n==1){
                c.add(a.remove(a.size()-1));
            }
            //先将a上n-1个盘子移到b
            dfs1(a,c,b,n-1);
            c.add(a.remove(a.size()-1));
            //将b放到a
            dfs1(b,a,c,n-1);
        }
        //合并两个有序链表

        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1==null){
                return list2;
            }
            if(list2==null){
                return list1;
            }
            if(list1.val<=list2.val){
                list1.next=mergeTwoLists(list1.next,list2);
                return list1;
            }else{
                list2.next=mergeTwoLists(list1,list2.next);
                return list2;
            }
        }
       //反转链表
       public ListNode reverseList(ListNode head) {
            //判断为空:没有节点或者只有一个节点
           if(head==null || head.next==null){
               return head;
           }
           ListNode newhead=reverseList(head.next);
           head.next.next=head;
           head.next=null;
          return newhead;
       }
       //两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
         //判断节点为空：只有一个节点或者没有
        if(head==null ||head.next==null){
            return head;
        }
        ListNode tmp=swapPairs(head.next.next);
        ListNode newHead=head.next;
        head.next.next=head;
        head.next=null;
        return newHead;
    }
   // pow(x,n)
   public double myPow(double x, long n) {
       if(n>0){
           return Pow(x,n);
       }else{
           return 1.0/Pow(x,-n);
       }
   }
    public double Pow(double x,long n){
        if(n==0){
            return 1.0;
        }
        double tmp=Pow(x,n/2);
        if(n%2==1){
            return tmp*tmp*x;
        }
        return tmp*tmp;
    }
    //计算布尔二叉树的值
    public boolean evaluateTree(TreeNode root) {
          if(root.left==null && root.right==null){
              if(root.val==0){
                  return false;
              }else{
                  return true;
              }
          }
          boolean left=evaluateTree(root.left);
          boolean right=evaluateTree(root.right);
          return root.val==2?left|right :left & right;
    }
}
